// https://www.lintcode.com/problem/hamming-distance/

public class Solution {
    /**
     * @param x: an integer
     * @param y: an integer
     * @return: return an integer, denote the Hamming Distance between two integers
     */
    public int hammingDistance(int x, int y) {
        // write your code here
        int ret = 0;
        String sx = toBin(x);
        String sy = toBin(y);
        int sxlen = sx.length();
        int sylen = sy.length();
        int diff = sxlen - sylen;
        if (diff < 0) {
            sx = padding(sx, -diff);
        } else if (diff > 0) {
            sy = padding(sy, diff);
        }
        for (int i = 0; i < sx.length(); ++i) {
            if (sx.charAt(i) != sy.charAt(i)) {
                ++ret;
            }
        }
        return ret;
    }
    
    protected String toBin(int x) {
        StringBuilder sb = new StringBuilder();
        while (x > 0) {
            sb.append(x % 2);
            x /= 2;
        }
        if (x > 0) {
            sb.append(x);
        }
        return sb.reverse().toString();
    }
    
    protected String padding(String s, int zeroes) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < zeroes; ++i) {
            sb.append(0);
        }
        sb.append(s);
        return sb.toString();
    }
}